π§· μ΅μ₯ μ¦κ° μμ΄
κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄(Longest Increasing Sequence)λ‘, μΌλ°μ μΌλ‘λ DPλ₯Ό μ΄μ©ν΄ ν΄κ²°νλ€.
{7, 2, 3, 8, 4, 5} -> LIS -> {2, 3, 4, 5}
πͺ DPλ₯Ό νμ©ν ꡬν λ° μκ° λ³΅μ‘λ
int[] arr = {7, 2, 3, 8, 4, 5};
int[] dp = new int[arr.length]; // LIS μ μ₯ λ°°μ΄
int max = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[i] > arr[j]) {
dp[i] = (dp[i] < dp[j] + 1) ? dp[j] + 1 : dp[i];
if (max < dp[i]) max = dp[i];
}
}
}
int[] answer = new int[max + 1];
int check = dp[dp.length - 1];
for (int i = dp.length - 1; i >= 0; i--) {
if (dp[i] == check) {
answer[check] = arr[i];
check--;
}
}
// DPμ μ μ₯λ κ° μ€ μ΅λκ° + 1μ΄ LISμ κΈΈμ΄
System.out.println(Arrays.toString(answer));
νμ§λ§ μμ κ°μ΄ DPλ₯Ό νμ©νλ λ°©μμ μκ° λ³΅μ‘λλ μ΄λ€.
μ΄λ₯Ό μ€μ΄λ μ’μ λ°©λ²μ μ΄λΆ νμμ νμ©νλ κ²μ΄λ€.
πͺ μ΄λΆ νμμ νμ©ν ꡬν λ° μκ° λ³΅μ‘λ
LISλ₯Ό ꡬμ±ν λ μ΄λΆ νμμ νμ©νλ€.
- LISμ ννλ₯Ό μ μ§νκΈ° μν΄ μ£Όμ΄μ§ λ°°μ΄μ μΈλ±μ€λ₯Ό νλμ© μ΄ν΄λ³Έλ€.
- ν΄λΉ μ«μκ° λ€μ΄κ° μμΉλ₯Ό μ΄λΆ νμμΌλ‘ νμν΄ μ½μ νλ€.
μΌλ°μ μΌλ‘ μ΄λΆ νμμ μκ° λ³΅μ‘λλ μ΄λ€. λ°λΌμ μ΄λ₯Ό μ΄μ©ν΄ μκ° λ³΅μ‘λλ₯Ό μΌλ‘ μ€μΌ μ μλ€.
static int[] arr = {7, 2, 3, 8, 4, 5};
static ArrayList<Integer> lis = new ArrayList<>();
public static void main(String[] args) {
lis.add(arr[0]);
int idx = 1;
int j = 0;
while(idx < arr.length) {
if (lis.get(j) < arr[idx]) {
lis.add(arr[idx]);
j++;
} else {
lis.remove(j);
lis.add(binarySearch(j, arr[idx]), arr[idx]);
}
idx++;
}
System.out.println(j + 1);
System.out.println(lis);
}
private static int binarySearch(int right, int target) {
// νμ leftλ μμμ
int left = 0;
int mid;
while(left < right) {
mid = (left + right) / 2;
if (lis.get(left) < target) left = mid + 1;
else right = mid;
}
return right;
}